package com.JingYan.HuaWei;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @program: JingYan
 * @ClassName: JK014.java
 * @author: Dong
 * @version: 1.0.0
 * @Description: 华为机考 第k个排列
 * @createTime 2024年04月10日 22:40:00
 */
public class JK013 {
    /**
     * 给定参数n，从1到n会有n个整数：1,2,3,…,n，这n个数字共有 n! 种排列。
     * 按大小顺序升序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
     * “123”
     * “132”
     * “213”
     * “231”
     * “312”
     * “321”
     * 给定 n 和 k，返回第 k 个排列。
     * 输入描述:
     * 输入两行，第一行为n，第二行为k，给定 n 的范围是 [1,9]，给定 k 的范围是[1,n!]。
     * 输出描述:
     * 输出排在第k位置的数字。
     * 示例1：
     * 输入
     * 3
     * 3
     * 输出
     * 213
     * 说明
     * 3的排列有123 132 213…，那么第3位置的为213
     * 示例2：
     * 输入
     * 2
     * 2
     * 输出
     * 21
     * 说明
     * 2的排列有12 21，那么第2位置的为21
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int ni = sc.nextInt(); // 读取n的值，即数字的范围[1,9]
        int kLine = sc.nextInt(); // 读取k的值，即要找的排列的序号[1,n!]

        // 初始化一个列表，用于存储从1到n的所有整数
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= ni; i++) {
            list.add(i);
        }

        int idx = ni; // idx用于记录剩余数字的数量
        StringBuilder sb = new StringBuilder(); // 用于构建最终的排列字符串
        kLine--; // 将k减1，因为列表的索引是从0开始的

        // 当列表中还有数字时，继续寻找下一个数字
        while (list.size() > 0) {
            int total = 1; // total用于存储(n-1)!的值
            // 计算(n-1)!，即剩余数字的全排列数量
            for (int i = idx - 1; i > 0; i--) {
                total *= i;
            }
            // 计算当前位的数字索引
            int index = kLine / total;
            // 更新kLine，为下一轮计算准备
            kLine = Math.max(kLine - total * index, 0);

            // 获取并添加当前位的数字到结果中
            int res = list.get(index);
            sb.append(res);
            // 从列表中移除已经使用的数字
            list.remove(index);
            // 减少剩余数字的计数
            idx--;
        }
        // 输出最终的排列
        System.out.println(sb);
    }

}
